﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

using GKS.Extensions.String.PatternMatching;

namespace GKS.Extensions.String.PatternMatching {
    
    /// <summary>
    /// This class contains the implementations of the Boyer-Moore pattern matching algorithms. 
    /// Both the implementations, for the "bad character shift" rule and the "good suffix shift" rule, are included.
    /// For more information regarding the algorithm visit: http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm 
    /// </summary>
    public static class BoyerMooreAlgorithm {

        #region bad character shift rule
        /// <summary>
        /// An implementation of the "bad character shift" rule of the Boyer-Moore algorithm.
        /// </summary>
        /// <param name="text">The string in which we must find the pattern.</param>
        /// <param name="pattern">The pattern to search for.</param>
        /// <param name="alphabet">The alphabet used in the text and the pattern.</param>
        /// <param name="comparisons">The number of comparisons executed by the algorithm.</param>
        /// <returns>The indexes in which the pattern appears in the text.</returns>
        public static int[] BadCharacterShiftRuleImplementation(this string text, string pattern, char[] alphabet, out int comparisons) {
            List<int> indexes = new List<int>();
            comparisons = 0;
            var preprocessingResult = pattern.BadCharacterShiftRulePreprocessing(alphabet);
            int j, charPosition;

            for (int i = pattern.Length - 1; i < text.Length;) {
                j = 0;

                while (j < pattern.Length && text.ElementAt(i - j).Equals(pattern.ElementAt(pattern.Length - j - 1))) {
                    comparisons++;
                    j++;
                }

                if (j == pattern.Length) {      // the pattern just appeared in the text
                    // add the position of the pattern in the text
                    indexes.Add(i + 1 - j);
                    i++;
                } else {    // the pattern has not yet appeared in the text
                    // get the greatest position of the mismatching character on the left side of the pattern
                    var indexesToUse = preprocessingResult[text.ElementAt(i - j)].Select(e => e).Where(e => e < (pattern.Length - 1 - j));      // the indexes that are on the left

                    if (indexesToUse.Count() > 0) {
                        indexesToUse = indexesToUse.OrderByDescending(e => e);      // order indexes from the greatest to the smallest
                        charPosition = indexesToUse.First();                        // pick the greatest
                        i += pattern.Length - 1 - j - charPosition;         // shift the index used to go through the text by the right amount of positions
                    } else {
                        i++;
                    }

                    comparisons++;
                }
            }

            return indexes.ToArray();
        }

        /// <summary>
        /// An implementation of the "bad character shift" rule of the Boyer-Moore algorithm.
        /// </summary>
        /// <param name="text">The string in which we must find the pattern.</param>
        /// <param name="pattern">The pattern to search for.</param>
        /// <param name="comparisons">The number of comparisons executed by the algorithm.</param>
        /// <returns>The indexes in which the pattern appears in the text.</returns>
        /// <remarks>The alphabet of the strings is retrieved automatically.</remarks>
        public static int[] BadCharacterShiftRuleImplementation(this string text, string pattern, out int comparisons) {
            return text.BadCharacterShiftRuleImplementation(pattern, (text + pattern).GetAlphabet(), out comparisons);
        }

        /// <summary>
        /// A method that does the preprocessing of a string for a "bad character shift" rule implementation of the Boyer-Moore algorithm.
        /// </summary>
        /// <param name="text">The text that has to be preprocessed.</param>
        /// <param name="alphabet">The alphabet used for the string.</param>
        /// <returns>The positions of the characters of the dictionary in the string.</returns>
        public static Dictionary<char, List<int>> BadCharacterShiftRulePreprocessing(this string text, char[] alphabet) {
            Dictionary<char, List<int>> characterPositions = new Dictionary<char, List<int>>();

            foreach (char c in alphabet) {
                // add the new <key, value> pair in the dictionary
                characterPositions.Add(c, new List<int>());
            }

            for (int i = 0; i < text.Length; i++) {
                // add in the dictionary the position of the current character of this string
                characterPositions[text.ElementAt(i)].Add(i);
            }

            return characterPositions;
        }
        #endregion

        #region good suffix rule
        /// <summary>
        /// An implementation of the "good suffix" rule of the Boyer-Moore algorithm.
        /// </summary>
        /// <param name="text">The string in which we must find the pattern.</param>
        /// <param name="pattern">The pattern to search for.</param>
        /// <param name="alphabet">The alphabet used in the text and the pattern.</param>
        /// <param name="comparisons">The number of comparisons executed by the algorithm.</param>
        /// <returns>The indexes in which the pattern appears in the text.</returns>
        public static int[] GoodSuffixRuleImplementation(this string text, string pattern, char[] alphabet, out int comparisons) {
            comparisons = 0;
            List<int> indexesList = new List<int>();

            if (pattern.Length > 0 && pattern.Length <= text.Length) {
                Dictionary<char, int> jumpTable = pattern.MakeJumpTable(alphabet);
                int[] offsetTable = pattern.MakeOffsetTable();

                for (int i = pattern.Length - 1, j; i < text.Length; ) {
                    for (j = pattern.Length - 1; j >= 0 && pattern.ElementAt(j).Equals(text.ElementAt(i)); i--, j--) {
                        comparisons++;

                        if (j == 0) { indexesList.Add(i); }
                    }

                    if (j >= 0) { comparisons++; } 
                    else {
                        j++;
                        i++;
                    }

                    i += Math.Max(offsetTable[pattern.Length - 1 - j], jumpTable[text.ElementAt(i)]);
                }
            }

            return indexesList.ToArray();
        }

        /// <summary>
        /// An implementation of the "good suffix" rule of the Boyer-Moore algorithm.
        /// </summary>
        /// <param name="text">The string in which we must find the pattern.</param>
        /// <param name="pattern">The pattern to search for.</param>
        /// <param name="comparisons">The number of comparisons executed by the algorithm.</param>
        /// <returns>The indexes in which the pattern appears in the text.</returns>
        /// <remarks>The alphabet is retrieved automatically by the text and pattern.</remarks>
        public static int[] GoodSuffixRuleImplementation(this string text, string pattern, out int comparisons) {
            return text.GoodSuffixRuleImplementation(pattern, (text + pattern).GetAlphabet(), out comparisons);
        }

        #region preprocessing
        /// <summary>
        /// A method that makes the jump table based on the mismatched character information.
        /// </summary>
        /// <param name="pattern">The pattern to analyze.</param>
        /// <param name="alphabet">The alphabet used for the pattern.</param>
        /// <returns>The jump table based on the mismatched character information.</returns>
        private static Dictionary<char, int> MakeJumpTable(this string pattern, char[] alphabet) {
            Dictionary<char, int> jumpTable = new Dictionary<char, int>();

            // inserting all the elements in the jump table
            foreach (char c in alphabet) { jumpTable.Add(c, alphabet.Length); }

            // setting the correct values in the jump table
            for (int i = 0; i < pattern.Length - 1; i++) { jumpTable[pattern.ElementAt(i)] = pattern.Length - 1 - i; }

            return jumpTable;
        }

        /// <summary>
        /// A method that makes the jump table based on the scan offset which mismatch occurs.
        /// </summary>
        /// <param name="pattern">The pattern to analyze.</param>
        /// <param name="alphabet">The alphabet used for the pattern.</param>
        /// <returns>The jump table based on the scan offset which mismatch occurs.</returns>
        private static int[] MakeOffsetTable(this string pattern) {
            int[] offsetTable = new int[pattern.Length];
            int lastPrefixPosition = pattern.Length;
            int suffixLength;

            for (int i = pattern.Length - 1; i >= 0; i--) {
                if (pattern.IsPrefix(i + 1)) { lastPrefixPosition = i + 1; }

                offsetTable[pattern.Length - 1 - i] = lastPrefixPosition - i + pattern.Length - 1;
            }

            for (int i = 0; i < pattern.Length - 1; i++) {
                suffixLength = pattern.SuffixLength(i);
                offsetTable[suffixLength] = pattern.Length - 1 - i + suffixLength;
            }

            return offsetTable;
        }

        /// <summary>
        /// A method that checks if pattern[position..pattern.length] is a prefix of pattern.
        /// </summary>
        /// <param name="pattern">The pattern to analyze.</param>
        /// <param name="position">The position to start the check from.</param>
        /// <returns>TRUE if pattern[position..pattern.length] is a prefix of pattern. FALSE otherwise.</returns>
        private static bool IsPrefix(this string pattern, int position) {
            int i, j;

            for (i = position, j = 0; i < pattern.Length && pattern.ElementAt(i).Equals(pattern.ElementAt(j)); i++, j++) ;

            return i == pattern.Length ? true : false;
        }

        /// <summary>
        /// A method that calculates the maximum length of the substring that ends in the given position and is a suffix.
        /// </summary>
        /// <param name="pattern">The pattern that must be analyzed.</param>
        /// <param name="position">The position from which the check must start.</param>
        /// <returns>The maximum length of the substring that ends in the given position and is a suffix.</returns>
        private static int SuffixLength(this string pattern, int position) {
            int length = 0;

            for (int i = position, j = pattern.Length - 1; i >= 0 && pattern.ElementAt(i).Equals(pattern.ElementAt(j)); i--, j--, length++) ;
            
            return length;
        }
        #endregion

        ///// <summary>
        ///// An implementation of the "good suffix" rule of the Boyer-Moore algorithm.
        ///// </summary>
        ///// <param name="text">The string in which we must find the pattern.</param>
        ///// <param name="pattern">The pattern to search for.</param>
        ///// <param name="alphabet">The alphabet used in the text and the pattern.</param>
        ///// <param name="comparisons">The number of comparisons executed by the algorithm.</param>
        ///// <returns>The indexes in which the pattern appears in the text.</returns>
        //public static int[] GoodSuffixRuleImplementation(this string text, string pattern, char[] alphabet, out int comparisons) {
        //    comparisons = 0;
        //    return null;
        //}

        ///// <summary>
        ///// An implementation of the "good suffix" rule of the Boyer-Moore algorithm.
        ///// </summary>
        ///// <param name="text">The string in which we must find the pattern.</param>
        ///// <param name="pattern">The pattern to search for.</param>
        ///// <param name="comparisons">The number of comparisons executed by the algorithm.</param>
        ///// <returns>The indexes in which the pattern appears in the text.</returns>
        //public static int[] GoodSuffixRuleImplementation(this string text, string pattern, out int comparisons) {
        //    return text.GoodSuffixRuleImplementation(pattern, text.GetAlphabet(), out comparisons);
        //}

        //public static void GoodSuffixRulePreprocessing(this string text, char[] alphabet) {
        //    int numberOfComparisons;
        //    char[] reverseText = text.Reverse().ToArray();         // here we have the array of characters in reverse order from the original text.
        //    string tmp = new string(reverseText);
        //    Dictionary<string, int[]> zPreprocessingResult = tmp.Preprocessing(out numberOfComparisons);
        //    //Dictionary<string, int[]> correctIndexes = new Dictionary<string, int[]>();

        //    //foreach (var key in zPreprocessingResult.Keys) {
        //    //    correctIndexes.Add(key, zPreprocessingResult[key]);
        //    //}

        //    int[] z = zPreprocessingResult["z"];
        //    int[] r = zPreprocessingResult["r"];
        //    int[] l = zPreprocessingResult["l"];

        //    for (int i = 0; i < z.Length; i++) {

        //    }

        //    //int[,] L;
        //    //int[,] L1;
        //    //int[,] l1;


        //}
        #endregion

        #region utility methods
        /// <summary>
        /// A method that retrieves the alphabet used in this string.
        /// </summary>
        /// <param name="text">The string that has to be analyzed.</param>
        /// <returns>The alphabet used to build this string.</returns>
        public static char[] GetAlphabet(this string text) {
            Dictionary<char, int> alphabet = new Dictionary<char, int>();
            char auxiliaryChar;

            for (int i = 0; i < text.Length; i++) {
                auxiliaryChar = text.ElementAt(i);

                if (!alphabet.Keys.Contains(auxiliaryChar)) {
                    // add the character to the alphabet
                    alphabet.Add(auxiliaryChar, i);
                }
            }

            return alphabet.Keys.ToArray();
        }
        #endregion
    }
}
